package com.wkh.datastructure;

import java.util.Iterator;
import java.util.function.Consumer;

//单向链表
public class SinglyLinkedList<E> implements Iterable<Object>{
    private Node head = new Node(99,null);//头节点

    //添加结点  从头部插入结点
    public void addFirst(E value){
        insert(0,value);
    }

    //添加结点  从尾部插入结点
    public void addLast(E value){
        Node last = findLast();
        last.next = new Node(value,null);
    }

    public E get(int index){
        Node node = findNode(index);
        if (node == null){
            throw new IllegalArgumentException("index:"+index+" 不合法");
        }
        return (E) node.value;
    }

    //像索引位置插入结点
    public void insert(int index,E value){
        //查找对应结点的上一个结点
        Node prevNode = findNode(index - 1);
        if (prevNode == null){//找不到
            throw new IllegalArgumentException("index:"+index+" 不合法");
        }
        prevNode.next = new Node(value,prevNode.next);
    }

    //删除第一个结点
    public void removeFirst(){
        remove(0);
    }

    //删除指定索引的结点
    public void remove(int index){
        Node prevNode = findNode(index - 1);//前一个结点
        if (prevNode == null){
            throw new IllegalArgumentException("index:"+index+" 不合法");
        }
        Node removed= prevNode.next;//当前删除的结点
        if (removed == null){
            throw new IllegalArgumentException("index:"+index+" 不合法");
        }
        prevNode.next = removed.next;
    }
    //查找对应索引处的结点
    private Node findNode(int index){
        int i = -1;//哨兵的索引位置
        for (Node p = head; p != null; p = p.next,i++) {
            if (i == index){
                return p;
            }
        }
        //没找到返回null
        return null;
    }

    //找到最后一个结点
    private Node findLast() {
        Node point = head;
        while (point.next != null){
            point = point.next;
        }
        return point;
    }

    //遍历链表
    public void loopWhile(Consumer<Object> consumer){
        Node pointer = head.next;
        while (pointer != null){
           consumer.accept(pointer.value);
            pointer = pointer.next;
        }
    }
    //遍历链表
    public void loopFor(Consumer<Object> consumer){
        for (Node p = head.next; p != null; p = p.next){
            consumer.accept(p.value);
        }
    }

    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     * iterate遍历
     * 迭代器遍历
     */
    @Override
    public Iterator<Object> iterator() {
        return new Iterator<Object>() {
            Node p = head.next;
            @Override
            public boolean hasNext() { //是否有下一个元素
                return p != null;
            }

            @Override
            public Object next() { //返回当前值并指向下一个元素
                Object value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    //内部类：隐藏实现细节
    private static class Node{
        Object value;//存放数据
        Node next;//指向下一个结点

        public Node(Object value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}

